// @algorithm @lc id=84 lang=cpp 
// @title largest-rectangle-in-histogram


#define print(...)
// @test([2,1,5,6,2,3])=10
// @test([2,4])=4
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        list<int> stk;
        vector<int> leftFirstShort(n, -1);
        for(int i=0; i<n; i++){
            while(stk.size() && heights[stk.back()] >= heights[i])
                stk.pop_back();
            if(stk.size())
                leftFirstShort[i] = stk.back();
            stk.push_back(i);
        }
        print("left:", leftFirstShort, "\n")
        
        stk.clear();
        vector<int> rightFirstShort(n, n);
        for(int i=n-1; i>=0; i--){
            while(stk.size() && heights[stk.back()] >= heights[i])
                stk.pop_back();
            if(stk.size())
                rightFirstShort[i] = stk.back();
            stk.push_back(i);
        }
        print("right:", rightFirstShort, "\n")

        int ans = 0;
        for(int i=0; i<n; i++)
            ans = max(ans, (rightFirstShort[i]-leftFirstShort[i]-1) * heights[i]);
        return ans;
    }
};